#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

// 包含排序算法的头文件
#include "bubble_sort.h"
#include "selection_sort.h"
#include "insertion_sort.h"
#include "quick_sort.h"
#include "merge_sort.h"
#include "heap_sort.h"

// 用于生成随机数组的函数
void generateRandomArray(int arr[], int n, int maxVal = 10000) {
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % maxVal;
    }
}

// 用于复制数组的函数
void copyArray(const int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试排序算法性能的函数
template<typename T>
void testSortFunction(T sortFunc, const char* name, int arr[], int n) {
    int tempArr[n];
    copyArray(arr, tempArr, n);

    clock_t start, end;
    double cpu_time_used;

    start = clock();
    sortFunc(tempArr, n);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    std::cout << name << " took " << cpu_time_used << " seconds to sort the array." << std::endl;
}

//测试函数重载
template<typename T>
void testSortFunction(T sortFunc, const char* name, int arr[], int n ,int left, int right) {
    int tempArr[n];
    copyArray(arr, tempArr, n);

    clock_t start, end;
    double cpu_time_used;

    start = clock();
    sortFunc(tempArr, left, right);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    std::cout << name << " took " << cpu_time_used << " seconds to sort the array." << std::endl;
}
int main() {
    srand(time(0)); // 初始化随机数种子
    const int SIZE = 100000; // 数组大小
    int arr[SIZE];

    generateRandomArray(arr, SIZE);

    // 测试冒泡排序
    testSortFunction(bubbleSort, "Bubble Sort", arr, SIZE);

    // 测试选择排序
    testSortFunction(selectionSort, "Selection Sort", arr, SIZE);

    // 测试插入排序
    testSortFunction(insertionSort, "Insertion Sort", arr, SIZE);

    //测试快速排序
    testSortFunction(quickSort, "Quick Sort", arr, SIZE, 0, SIZE-1);

    //测试归并排序
    testSortFunction(mergeSort, "Merge Sort", arr, SIZE, 0, SIZE-1);

    //测试堆排序
    testSortFunction(heapSort, "Heap Sort", arr, SIZE);

    return 0;
}